home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 16 / CU Amiga Magazine's Super CD-ROM 16 (1997-10-16)(EMAP Images)(GB)[!][issue 1997-11].iso / CUCD / Graphics / Ghostscript / source / gsnogc.c < prev    next >
C/C++ Source or Header  |  1996-12-29  |  9KB  |  330 lines
  1. /* Copyright (C) 1996 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of Aladdin Ghostscript.
  4.   
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.   
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* gsnogc.c */
  20. /* String freelist implementation and ersatz garbage collector */
  21. #include "gx.h"
  22. #include "gsgc.h"
  23. #include "gsmdebug.h"
  24. #include "gsstruct.h"
  25. #include "gxalloc.h"
  26.  
  27. /*
  28.  * We implement string freelists here, because they are only useful
  29.  * in non-garbage-collected environments.
  30.  */
  31.  
  32. #define get2(ptr) (((ptr)[0] << 8) + (ptr)[1])
  33. #define put2(ptr, val) ((ptr)[0] = (val) >> 8, (ptr)[1] = (byte)(val))
  34.  
  35. #define imem ((gs_ref_memory_t *)mem)
  36.  
  37. /* Allocate a string. */
  38. /* Scan the current chunk's free list if the request is large enough. */
  39. /* Currently we require an exact match of the block size. */
  40. private byte *
  41. sf_alloc_string(gs_memory_t *mem, uint nbytes, client_name_t cname)
  42. {    if ( nbytes >= 40 && nbytes < imem->large_size )
  43.       { byte *base = csbase(&imem->cc);
  44.         byte *prev = 0;
  45.         uint offset = imem->cc.sfree;
  46.         uint next;
  47.         byte *ptr;
  48.  
  49.         for ( ; offset != 0; prev = ptr, offset = next )
  50.           { ptr = base + offset;
  51.             next = get2(ptr + 2);
  52.             if ( get2(ptr) != nbytes )
  53.           continue;
  54.         /* Take this block. */
  55.         if ( prev == 0 )
  56.           imem->cc.sfree = next;
  57.         else
  58.           put2(prev + 2, next);
  59.         if_debug4('A', "[a%d:+>F]%s(%u) = 0x%lx\n", imem->space,
  60.               client_name_string(cname), nbytes, (ulong)ptr);
  61.         gs_alloc_fill(ptr, gs_alloc_fill_alloc, nbytes);
  62.         imem->lost.strings -= nbytes;
  63.         return ptr;
  64.           }
  65.       }
  66.     return (*gs_ref_memory_procs.alloc_string)(mem, nbytes, cname);
  67. }
  68.  
  69. /* Free a string. */
  70. private void
  71. sf_free_string(gs_memory_t *mem, byte *str, uint size, client_name_t cname)
  72. {    chunk_t *cp;
  73.     uint str_offset;
  74.  
  75.     if ( str == imem->cc.ctop )
  76.       {    if_debug4('A', "[a%d:-> ]%s(%u) 0x%lx\n", imem->space,
  77.               client_name_string(cname), size, (ulong)str);
  78.         imem->cc.ctop += size;
  79.         gs_alloc_fill(str, gs_alloc_fill_free, size);
  80.         return;
  81.       }
  82.     if_debug4('A', "[a%d:->#]%s(%u) 0x%lx\n", imem->space,
  83.           client_name_string(cname), size, (ulong)str);
  84.     imem->lost.strings += size;
  85.     if ( ptr_is_in_chunk(str, &imem->cc) )
  86.       cp = &imem->cc;
  87.     else
  88.       { chunk_locator_t loc;
  89.         loc.memory = imem;
  90.         loc.cp = imem->clast;
  91.         if ( !chunk_locate_ptr(str, &loc) )
  92.           return;    /* something is probably wrong.... */
  93.         cp = loc.cp;
  94.       }
  95.     if ( str == cp->ctop )
  96.       { cp->ctop += size;
  97.         return;
  98.       }
  99.     str_offset = str - csbase(cp);
  100.     if ( size >= 4 )
  101.       { byte *prev;
  102.         uint next;
  103.  
  104.         put2(str, size);
  105.         if ( cp->sfree == 0 || str_offset < cp->sfree )
  106.           { /* Put the string at the head of the free list. */
  107.         put2(str + 2, cp->sfree);
  108.         cp->sfree = str_offset;
  109.         return;
  110.           }
  111.         /* Insert the new string in address order. */
  112.         prev = csbase(cp) + cp->sfree;
  113. #ifdef DEBUG
  114.         if ( gs_debug_c('?') )
  115.           { if ( prev < str + size && prev + get2(prev) > str )
  116.           { lprintf4("freeing string 0x%lx(%u), overlaps 0x%lx(%u)!\n",
  117.                  (ulong)str, size, (ulong)prev, get2(prev));
  118.             return;
  119.           }
  120.           }
  121. #endif
  122.         for ( ; ; )
  123.           { next = get2(prev + 2);
  124. #ifdef DEBUG
  125.         if ( gs_debug_c('?') && next != 0 )
  126.           { byte *pnext = csbase(cp) + next;
  127.             if ( pnext < str + size && pnext + get2(pnext) > str )
  128.               { lprintf4("freeing string 0x%lx(%u), overlaps 0x%lx(%u)!\n",
  129.                  (ulong)str, size, (ulong)pnext, get2(pnext));
  130.                 return;
  131.               }
  132.           }
  133. #endif
  134.             if ( next >= str_offset || next == 0 )
  135.           break;
  136.         prev = csbase(cp) + next;
  137.           }
  138.         put2(str + 2, next);
  139.         put2(prev + 2, str_offset);
  140.         gs_alloc_fill(str + 4, gs_alloc_fill_free, size - 4);
  141.       }
  142.     else
  143.       { /* Insert the string in the 1-byte free list(s).  Note that */
  144.         /* if it straddles a 256-byte block, we need to do this twice. */
  145.         ushort *pfree1 = &cp->sfree1[str_offset >> 8];
  146.         uint count = size;
  147.         byte *prev;
  148.         byte *ptr = str;
  149.  
  150.         if ( *pfree1 == 0 )
  151.           { *str = 0;
  152.         *pfree1 = str_offset;
  153.         prev = str;
  154.           }
  155.         else if ( str_offset < *pfree1 )
  156.           { *str = *pfree1 - str_offset;
  157.         *pfree1 = str_offset;
  158.         prev = str;
  159.           }
  160.         else
  161.           { uint next;
  162.         prev = csbase(cp) + *pfree1;
  163.         while ( prev + (next = *prev) < str )
  164.           prev += next;
  165.           }
  166.         for ( ; ; )
  167.           { /*
  168.          * Invariants:
  169.          *    prev < sfbase + str_offset
  170.          *    *prev == 0 || prev + *prev > sfbase + str_offset
  171.          */
  172.         *ptr = (*prev == 0 ? 0 : prev + *prev - ptr);
  173.         *prev = ptr - prev;
  174.         if ( !--count )
  175.           break;
  176.         prev = ptr++;
  177.         if ( !(++str_offset & 255) )
  178.           { /* Move to the next block of 256 bytes. */
  179.             ++pfree1;
  180.             *ptr = (byte)*pfree1;
  181.             *pfree1 = str_offset;
  182.             if ( !--count )
  183.               break;
  184.             prev = ptr++;
  185.             ++str_offset;
  186.           }
  187.           }
  188.       }
  189. }
  190.  
  191. /* Enable or disable freeing. */
  192. private void
  193. sf_enable_free(gs_memory_t *mem, bool enable)
  194. {    (*gs_ref_memory_procs.enable_free)(mem, enable);
  195.     if ( enable )
  196.       mem->procs.free_string = sf_free_string;
  197. }
  198.  
  199. #undef imem
  200.  
  201. /* Merge free strings at the bottom of a chunk's string storage. */
  202. private void
  203. sf_merge_strings(chunk_t *cp)
  204. {    for ( ; ; )
  205.       { byte *ctop = cp->ctop;
  206.         uint top_offset = ctop - csbase(cp);
  207.         ushort *pfree1;
  208.  
  209.         if ( cp->sfree == top_offset )
  210.           { /* Merge a large free block. */
  211.         cp->sfree = get2(ctop + 2);
  212.         cp->ctop += get2(ctop);
  213.         continue;
  214.           }
  215.         if ( !cp->sfree1 )
  216.           break;
  217.         pfree1 = &cp->sfree1[top_offset >> 8];
  218.         if ( *pfree1 != top_offset )
  219.           break;
  220.         /* Merge a small (1-byte) free block. */
  221.         *pfree1 = (*ctop ? *pfree1 + *ctop : 0);
  222.         cp->ctop++;
  223.       }
  224. }
  225.  
  226. /*
  227.  * This procedure has the same API as the garbage collector used by the
  228.  * PostScript interpreter, but it is designed to be used in environments
  229.  * that don't need garbage collection and don't use save/restore.  All it
  230.  * does is coalesce free blocks at the high end of the object area of each
  231.  * chunk, and free strings at the low end of the string area, and then free
  232.  * completely empty chunks.
  233.  */
  234.  
  235. void
  236. gs_reclaim(vm_spaces *pspaces, bool global)
  237. {    int space;
  238.     gs_ref_memory_t *mem_prev = 0;
  239.  
  240.     for ( space = 0; space < countof(pspaces->indexed); ++space )
  241.       { gs_ref_memory_t *mem = pspaces->indexed[space];
  242.         chunk_t *cp;
  243.         chunk_t *cprev;
  244.         /*
  245.          * We're going to recompute lost.objects, by subtracting the
  246.          * amount of space reclaimed minus the amount of that space that
  247.          * was on free lists.
  248.          */
  249.         ulong found = 0;
  250.  
  251.         if ( mem == 0 || mem == mem_prev )
  252.           continue;
  253.         mem_prev = mem;
  254.         alloc_close_chunk(mem);
  255.  
  256.         /*
  257.          * Change the allocator to use string freelists in the future.
  258.          */
  259.         mem->procs.alloc_string = sf_alloc_string;
  260.         if ( mem->procs.free_string != gs_ignore_free_string )
  261.           mem->procs.free_string = sf_free_string;
  262.         mem->procs.enable_free = sf_enable_free;
  263.  
  264.         /* Visit chunks in reverse order to encourage LIFO behavior. */
  265.         for ( cp = mem->clast; cp != 0; cp = cprev )
  266.           { obj_header_t *begin_free = (obj_header_t *)cp->cbase;
  267.  
  268.         cprev = cp->cprev;
  269.             SCAN_CHUNK_OBJECTS(cp)
  270.         DO_ALL
  271.           if ( pre->o_type == &st_free )
  272.             { if ( begin_free == 0 )
  273.                 begin_free = pre;
  274.             }
  275.           else
  276.             begin_free = 0;
  277.         END_OBJECTS_SCAN
  278.         if ( !begin_free )
  279.           continue;
  280.         /* We found free objects at the top of the object area. */
  281.         found += (byte *)cp->cbot - (byte *)begin_free;
  282.         /* Remove the free objects from the freelists. */
  283.             { int i;
  284.               for ( i = 0; i < num_freelists; i++ )
  285.             { obj_header_t *pfree;
  286.               obj_header_t **ppfprev = &mem->freelists[i];
  287.               uint free_size =
  288.                 (i << log2_obj_align_mod) + sizeof(obj_header_t);
  289.  
  290.               while ( (pfree = *ppfprev) != 0 )
  291.                 if ( ptr_ge(pfree, begin_free) &&
  292.                  ptr_lt(pfree, cp->cbot)
  293.                    )
  294.                   { /* We're removing an object. */
  295.                 *ppfprev = *(obj_header_t **)pfree;
  296.                 found -= free_size;
  297.                   }
  298.                 else
  299.                   ppfprev = (obj_header_t **)pfree;
  300.             }
  301.             }
  302.             { byte *top = cp->ctop;
  303.               sf_merge_strings(cp);
  304.               mem->lost.strings -= cp->ctop - top;
  305.             }
  306.         if ( begin_free == (obj_header_t *)cp->cbase &&
  307.              cp->ctop == cp->climit
  308.            )
  309.           { /* The entire chunk is free. */
  310.             chunk_t *cnext = cp->cnext;
  311.  
  312.             alloc_free_chunk(cp, mem);
  313.             if ( mem->pcc == cp )
  314.               mem->pcc =
  315.             (cnext == 0 ? cprev : cprev == 0 ? cnext :
  316.              cprev->cbot - cprev->ctop > cnext->cbot - cnext->ctop ?
  317.              cprev : cnext);
  318.           }
  319.         else
  320.           { if_debug4('a', "[a]resetting chunk 0x%lx cbot from 0x%lx to 0x%lx (%lu free)\n",
  321.                   (ulong)cp, (ulong)cp->cbot, (ulong)begin_free,
  322.                   (ulong)((byte *)cp->cbot - (byte *)begin_free));
  323.             cp->cbot = (byte *)begin_free;
  324.           }
  325.           }
  326.         mem->lost.objects -= found;
  327.         alloc_open_chunk(mem);
  328.       }
  329. }
  330.